slope trick 3
Slope Trick 점화식 세우는 방법?
potatoes and fertilizers
이거를 예시로 보자. 나는 지금까지 보통 f(i,j)={d'[i]=j일때 최소비용}으로 정의해서 prefix min형태로 정리됬는데, d'[i]<=j로 정의하면 또 다른방식으로도 볼 수 있나봄. 근데 dp정의상 f(i,j)>=f(i,j+1)인걸 관찰해야되서 더 귀찮으려나?
이거를 예시로 보자. 나는 지금까지 보통 f(i,j)={d'[i]=j일때 최소비용}으로 정의해서 prefix min형태로 정리됬는데, d'[i]<=j로 정의하면 또 다른방식으로도 볼 수 있나봄. 근데 dp정의상 f(i,j)>=f(i,j+1)인걸 관찰해야되서 더 귀찮으려나?